package com.datastructure.test.entrylistnodeofloop;

import java.util.ArrayList;

public class EntryListNodeOfLoop {

    public static void main(String[] args) {

    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ArrayList<ListNode> data = new ArrayList<>();
        while (pHead!=null){
            for (int i = 0; i < data.size(); i++) {
                ListNode listNode = data.get(i);
                if(listNode.equals(pHead)){
                    return listNode;
                }
            }
            data.add(pHead);
            pHead=pHead.next;
        }
        return null;
    }
    public ListNode EntryNodeOfLoop1(ListNode pHead) {
        ListNode slow = pHead;//快指针
        ListNode fast = pHead;//慢指针
        while (fast != null && fast.next != null) {
//快慢指针，快指针每次走两步，慢指针每次走一步
            fast = fast.next.next;
            slow = slow.next;
//先判断是否有环，
            if (slow == fast) {
//确定有环之后才能找环的入口
                while (pHead != slow) {
//两指针，一个从头结点开始，
                    //一个从相遇点开始每次走一步，直到
                    //再次相遇为止
                    pHead = pHead.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
